package Lee_code;

import javafx.util.Pair;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;

/**
 * @author blh
 * @date 2024年09月17日 10:36
 */
public class Lee_1171_917 {
    public ListNode removeZeroSumSublists(ListNode head) {
        // 感觉是前缀hashMap
        // 先获得一个数组
        Deque<ListNode> deque = new ArrayDeque<>();
        ListNode dummy = head;
        while (dummy != null) {
            deque.add(dummy);
            dummy = dummy.next;
        }

        Deque<Integer> preSum = new ArrayDeque<>();
        int curSum = 0;

        while (head != null) {
            curSum = curSum + head.val;
            // 如果hashMap中有cur->中间有一段0
            if (preSum.contains(curSum)) {
                // 两个deque同时出
                while (!preSum.peekLast().equals(curSum)) {
                    preSum.pollLast();
                    deque.pollLast();
                }
                preSum.pollLast();
                deque.pollLast();
                if (preSum.isEmpty()) {
                    curSum = 0;
                } else {
                    curSum = preSum.getLast();
                }

            } else if (curSum == 0) {
                preSum.clear();
                deque.clear();
            } else {
                preSum.add(curSum);
                deque.add(head);
            }

            head = head.next;
        }
        ListNode temp = new ListNode();
        ListNode real = temp;
        for (ListNode listNode : deque) {
            temp.next = listNode;
            temp = temp.next;
            temp.next = null;
        }
        return real.next;
    }
}
